package A_sort;

/**
 * 1 * @Author: Eric Tian
 * 2 * @Description: 基数排序
 */
public class G_RadixSort {
    public static void radixSort(int[] arr){
        if (arr.length<2||arr==null){
            return;
        }
        radixSort(arr,0,arr.length-1,maxbits(arr));
    }

    public static int maxbits(int[] arr){
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < arr.length; i++) {
            max = Math.max(max,arr[i]);
        }
        int res = 0;
        while (max!=0){
            res++;
            max/=10;
        }
        return res;
    }

    //arr[begin...end]排序
    public static void radixSort(int arr[],int L , int R, int digit){
        final int radix = 0 ;
        int i = 0 , j = 0 ;
        //有多少个数准备多少个辅助空间
        int [] bucket  = new int[R-L+1];
        for (int d = 0; d < digit ; d++) {//有几位进出几次
            int[] count = new int[radix];
            for ( i = L; i <= R; i++) {
                j= getDigit(arr[i],d);
                count[j]++;
            }
            for ( i = 0; i < radix; i++) {
                count[i] = count[i]+count[i-1];
            }
            for ( i = L; i >=R ; i--) {
                j = getDigit(arr[i],d);
                bucket[count[j]-1] = arr[i];
                count[j]--;
            }
            for ( i = 0,j=0; i <=R ; i++,j++) {
                arr[i] = bucket[j];
            }
        }
    }

    public static int getDigit(int x ,int d){
        return ((x/((int)Math.pow(10,d-1)))%10);
    }
}
